// https://www.lintcode.com/problem/maximum-subarray/description

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> &nums) {
        // 法1:贪心
        // max记录全局最大值，sum记录区间和，
        // 如果当前sum>0，那么可以继续和后面的数求和，否则就从0开始
        // 能记录每一段里面最大的数。（如果中间有更大的出现，那么开头的计算结果应该为
        // 。）
        
        int sum = 0, max_sum = INT_MIN;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            max_sum = max(sum, max_sum);
            sum = max(0, sum); //注意是sum<0之后置0，不是num
        }
        return max_sum;
        //法2：前缀和数组 + dp
        // int sum = 0, min_sum = 0, max_sum = INT_MIN;
        // for (int i = 0; i < nums.size(); ++i)
        // {
        //     sum += nums[i];
        //     max_sum = max(max_sum, sum - min_sum);
        //     min_sum = min(min_sum, sum);
        // }
        // return max_sum;
    }
};


// 原始
#include <iostream>
#include <vector>
using namespace std;

// To execute C++, please define "int main()"

// The TestCase is shown below
// Input : 1 2
// Output : 3

int getAns(vector<int>& nums) {
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> sum(n);
    sum[0] = nums[0];
    int ans = -2147483648;
    int rec = 2147483647;
    for (int i = 1; i < nums.size(); ++i) {
        sum[i] = sum[i - 1] + nums[i];
    }
    for (int i = 1; i < nums.size(); ++i) {
        rec = min(sum[i], rec);
        ans = max(sum[i] - rec, ans);
    }
    return ans;
}

int main() {
	vector<int> nums = {-2,1,-3,4,3,1};
    cout << getAns(nums) << endl;
  	return 0;
}